Cryptographic systems generally owe their security to the fact that a particular piece of information is kept secret without which it is almost impossible to break the scheme. This secret information must generally be stored within a secure boundary, making it difficult for an attacker to get at it directly. However, various schemes or attacks have been attempted in order to obtain this secret information. One of these is the timing attack.
By way of background current public key cryptographic schemes such as RSA and elliptic curve (EC) operate over mathematical groups Fp* and E(Fq) respectively. The group operations, called multiplication modulo p, in RSA, and addition of points in EC are repeated in a particular way to perform a scalar operation. In RSA the operand is called an exponent, the operation is called exponentiation and the method of multiplying is commonly known as repeated square-and-multiply. Thus given a number a ε Fp and an integer 0≦k<p, the exponent, whose binary representation is k=Σi=or ki2i a value ak mod p may be calculated by repeated use of the square-and-multiply algorithm. Similarly given g(x)εFpm and an integer 0≦k≦pm−1 then g(x)k mod ƒ(x) may be calculated by this method.
On the other hand, in EC the operand is a scalar multiplier, the operation is called scalar multiplication of a point, and the method is known as double-and-add. Thus if α is a positive integer and P is an elliptic curve point then aP may be obtained by the double-and-add method. Both these methods are well known in the art and will not be discussed further.
In RSA, half of all exponentiation operations use a private key. Whereas in EC all scalar multiplications use either a long term private key or a session private key. In each of these cases, the private key is safe due to the difficulty of reversing the exponentiation or multiplication operation as the case may be. This is based on the discrete log problem the difficulty of integer factorization. As mentioned earlier, an attacker once in possession of the private key (either long term or session) is able to forge signatures and or decrypt secret messages for the attacked entity. Thus it is paramount to maintain the secrecy or integrity of the private key in the system.
Many techniques have been suggested to obtain the private key. The encryption operations are performed either in a special purpose or general purpose processor operating in a cyclic manner. Recent attack methods proposed in open literature have been based on timing analysis of these processors or in other words timing analysis of ‘black box’ operations. In one instance an attacker by capturing the instantaneous power usage of a processor throughout a private key operation obtains a power signature. The power signature relates to the number of gates operating at each clock cycle. Each fundamental operation as described in the preceding paragraph generates a distinct timing pattern. Other methods exist for obtaining a power signature than instantaneous power usage.
Laborious but careful analysis of an end-to-end waveform can decompose the order of add-and-double or square-and-multiply operations. Either a double or square must occur for each bit of either the exponent or scalar multiplier respectively. Therefore, the places where double waveforms are adjacent each other represent bit positions with zeros and places where there are add patterns indicate bits with ones. Thus these timing measurements can be analyzed to find the entire secret key and thus compromise the system. Thus there is a need for a system which minimizes the risk of a successful timing attack.